package src.leetcode.tree.simple_0112;

import src.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;

public class hasPathSum {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7,8,9,10));
        TreeNode root = TreeNode.createTree(list);
        Solution solution = new Solution();
        System.out.println(solution.hasPathSum(root, 15)); // 输出 true
    }
}

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        int sum = node.val;
        while(node != null || !stack.isEmpty()){
            if(node != null){
                stack.addFirst(node);
                node = node.left;
            }else{
                node = stack.pollFirst();

                if(node.left == null && node.right == null && sum == targetSum){
                    return true;
                }
                node = node.right;
            }

        }
        return false;


    }
}
